The present invention relates generally to data compression/decompression schemes and, in particular, to a technique for compressing and decompressing data based on tokens and Huffman coding.
Wireless communication systems are well known in the art. In such systems, communications (particularly voice communications) are typically supported by a wireless infrastructure that supports wireless communications with and between one or more wireless communication devices (or mobile devices), such as cellular phones, portable two-way radios, wirelessly-enabled personal digital assistants, etc. Increasingly, suppliers of such mobile devices are working toward the provision of more than just voice communications. For example, in addition to audio information, such communication devices are now capable of providing image and video information to users.
Increasingly, information that can be provided by today""s mobile devices can be classified as static data items (i.e., data that is created once and used repeatedly thereafter) such as fonts, image libraries, audio libraries, prompts, dictionaries, etc. Such static items may often require substantial storage resources. Therefore, it is desirable to compress such data for delivery to, and/or storage in, mobile devices that typically have limited storage resources. Compression is typically a resource-intensive process, whereas decompression should be relatively fast and efficient. While the compression of static data items is typically performed once on relatively powerful host or network-based computers, decompression is performed repeatedly on such mobile devices. In order to maximize efficiency, it is further preferable that each particular data item within a collection of previously compressed items be randomly-accessible, i.e., capable of being decompressed individually without having to decompress the remainder of the collection.
While various techniques exist for performing such compression, they generally suffer from various shortcomings. For example, Huffman coding is known to provide reasonable compression performance while simultaneously preserving random accessibility of individual data items. Huffman coding may generally be applied to virtually any type of data, resulting in varying levels of compression efficiency. As used herein, compression efficiency or compression savings refers to ratios of compressed data size to uncompressed data size; improved efficiency or better savings results in lower ratios. Other techniques are known that improve the compression efficiency based on knowledge of the characteristics of the data to be compressed. Still other techniques, such as the so-called LZ77 or LZ78 techniques, also provide greater compression efficiency at the expense of random accessibility.
Therefore, it would be advantageous to provide a technique for compressing and decompressing data that provides good compression efficiency without the need for significant memory or other resource requirements, without requiring detailed knowledge of the characteristics of the data being compressed and that preserves random accessibility to individual data items.